package com.wang.transfer.util.algorithm;

import java.math.BigDecimal;
import java.util.Arrays;

/**
 * 最接近的三数之和
 * 整数数组中找出三个数之和与target值最接近的值
 */
public class ThreeNumClosest {

    public static void main(String[] args) {
        int[] nums = {-1,2,1,-4};
        int target = 1;
//        int i = new ThreeNumClosest().threeNumClosest(nums, target);
        int i = new ThreeNumClosest().threeNumClosest2(nums, target);
        System.out.println(i);
//        new ThreeNumClosest().bigDecimal();
    }

    public int threeNumClosest(int[] nums, int target) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for (int first = 0; first < n; ++first) {
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            for (int second = first + 1; second < n; ++second) {
                int third = n - 1;
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                while (second < third) {
                    int tar = nums[first] + nums[second] + nums[third];
                    if (tar == target) {
                        return target;
                    }
                    int target1 = Math.max(tar, target);
                    int target2 = Math.min(tar, target);
                    int target3 = Math.max(ans, target);
                    int target4 = Math.min(ans, target);
                    if (target1 - target2 < target3 - target4) {
                        ans = tar;
                    }
                    if (second == --third) {
                        break;
                    }
                }
            }
        }
        return ans;
    }

    public void bigDecimal() {
        BigDecimal bigDecimal = new BigDecimal("23.55");
        BigDecimal multiply = bigDecimal.multiply(new BigDecimal("1").add(new BigDecimal("12.00000000")));
        System.out.println(multiply);
    }

    public int threeNumClosest2(int[] nums, int target) {
        int n = nums.length;
        Arrays.sort(nums);
        int best = 1000000;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int j = i + 1, k = n - 1;
            while (j < k) {
                int num = nums[i] + nums[j] + nums[k];
                if (num == target) {
                    return target;
                }
                if (Math.abs(num - target) < Math.abs(best - target)) {
                    best = num;
                }
                if (num > target) {
                    int k0 = k - 1;
                    while (k0 > j && nums[k0] == nums[k]) {
                        k0--;
                    }
                    k = k0;
                } else {
                    int j0 = j + 1;
                    while (j0 < k && nums[j0] == nums[j]) {
                        j0++;
                    }
                    j = j0;
                }
            }
        }
        return best;
    }
}
